/*
 * @: 并查集
 * @Version: 1.0
 * @Autor: ziwei
 * @Date: 2022-02-24 11:03:59
 * @LastEditors: ziwei
 * @LastEditTime: 2022-03-11 18:07:06
 */
//染色法
//颜色即代表了集合的名字
//1.quick-find 合并慢 查找块
class UnisonSet{
  constructor(n=100){
    this.n = n;
    this.color = new Array(n);//这里存放结合的颜色
    this.init();
  }

  //将节点的颜色定义为自身的颜色
  init(){
    for(let i =0;i<this.n;i++){
      this.color[i]=i //集合颜色的初始化
    }
  }

  //查找属于哪个集合 复杂度O1
  find(x){
    return this.color[x]
  }

  //查询a,b是否属于一个集合
  query(a,b){
    return this.find(a)===this.find(b)
  }

  //让A集合的节点颜色 涂成b集合的节点
  merge(a,b){
    const colorA = this.color[a];
    for(let i=0;i<this.n;i++){
      if(this.color[a]===colorA){//并不是只有color[a]的颜色是color[a]
        //可能有好多颜色都是color[a]
        this.color[i] = this.color[b]
      }
    }
  }
}

//2.quick-union
class UnionSet2{
  constructor(n=100){
    this.n = n;
    //当前节点的父节点指向谁
    this.father = new Array(n);//这里存放结合的颜色
    this.init();
  }

  //将节点的父节点定义为自身
  init(){
    for(let i =0;i<this.n;i++){
      this.father[i]=i //集合父节点的初始化
    }
  }

  //查找x属于哪个集合,x的根根节点是谁
  find(x){
    //如果x的父亲节点是它自己， 那么x就是根节点
    if(this.father[x]==x) return x
    //否则我们就继续向上查找
    return this.find(this.father[i])
  }

  //查询a,b是否属于一个集合
  query(a,b){
    return this.find(a)===this.find(b)
  }

  //让A集合的节点颜色 涂成b集合的节点
  merge(a,b){
   const fa = this.find(a)
   const fb = this.find(b)
   if(fa===fb) return
   this.father[fa] = fb
  }
}

//3.weighted-queck-union 优化find方法 按秩合并
class UnionSet3{
  constructor(n=100){
    this.n = n;
    //当前节点的父节点指向谁
    this.father = new Array(n);//这里存放结合的颜色
    this.size = new Array(n);//存放当前集合的元素数量
    this.init();
  }

  //将节点的父节点定义为自身
  init(){
    for(let i =0;i<this.n;i++){
      this.father[i]=i //集合父节点的初始化
    }
  }

  //查找x属于哪个集合,x的根根节点是谁
  find(x){
    //如果x的父亲节点是它自己， 那么x就是根节点
    if(this.father[x]==x) return x
    //否则我们就继续向上查找
    root = this.find(this.father[x])
    //将x直接挂到根节点上
    this.father[x] = root;
    return root;
  }

  //查询a,b是否属于一个集合
  query(a,b){
    return this.find(a)===this.find(b)
  }

  //让A集合的节点颜色 涂成b集合的节点
  merge(a,b){
   const fa = this.find(a)
   const fb = this.find(b)
   if(fa===fb) return
   if(this.size[fa]<this.size[fb]){//a的节点少
     this.father[fa]=fb;//将a合并到b中
     this.size[fb]+=this.size[fa];//b集合的元素数量要加上a集合的数量
   }else{
     this.father[fb] = fa;//将b合并到a中
     this.size[fa] +=this.size[fb]
   }
  }
}

//4.带路压缩的weighted-queck-union
class UnionSet4{
  constructor(n=100){
    this.n = n;
    //当前节点的父节点指向谁
    this.father = new Array(n);//这里存放结合的颜色
    this.size = new Array(n);//存放当前集合的元素数量
    this.init();
  }

  //将节点的父节点定义为自身
  init(){
    for(let i =0;i<this.n;i++){
      this.father[i]=i //集合父节点的初始化
    }
  }

  //查找x属于哪个集合,x的根根节点是谁
  find(x){
    //如果x的父亲节点是它自己， 那么x就是根节点
    if(this.father[x]==x) return x;
    const root = this.find(this.father[x])
    //**将x直接挂到根节点上**//
    this.father[x] = root;
    return root;
  }

  //查询a,b是否属于一个集合
  query(a,b){
    return this.find(a)===this.find(b)
  }

  //让A集合的节点颜色 涂成b集合的节点
  merge(a,b){
   const fa = this.find(a)
   const fb = this.find(b)
   if(fa===fb) return
   if(this.size[fa]<this.size[fb]){//a的节点少
     this.father[fa]=fb;//将a合并到b中
     this.size[fb]+=this.size[fa];//b集合的元素数量要加上a集合的数量
   }else{
     this.father[fb] = fa;//将b合并到a中
     this.size[fa] +=this.size[fb]
   }
  }
}
function test() {
  const unionSet = new UnionSet4(100);
  unionSet.merge(3,1)
  unionSet.merge(1,4)
  console.log(`1属于集合${unionSet.find(1)}`);
  console.log(`4属于集合${unionSet.find(4)}`);
}